package com.lry.basic.algorithm.common;

/**
 * @author:刘仁有
 * @desc:
 * @email:953506233@qq.com
 * @data:2019/10/15
 */
public class SearchMatrix {
    public static void main(String[] args) {
        SearchMatrix searchMatrix = new SearchMatrix();
        System.out.println(searchMatrix.searchMatrix(new int[][]{{1, 4, 5, 7}, {10, 11, 16, 20}, {23, 30, 34, 50}}, 50));
    }

//    每行中的整数从左到右按升序排列。
//    每行的第一个整数大于前一行的最后一个整数。
    public boolean searchMatrix(int[][] matrix, int target) {
        if(null==matrix||matrix.length<=0||matrix[0].length<=0||target<matrix[0][0])return false;
        int i=0;//定位target在哪一行
        while(i<matrix.length&&target>=matrix[i][0]){
            if(target==matrix[i][0])return true;
            i++;
        }
        i-=1;
        int low = 0;
        int high = matrix[0].length-1;
        while(low<=high){
            int mid = (low+high)>>>1;
            if(target==matrix[i][mid]){
                return true;
            }else if(target>matrix[i][mid]){
                low = mid+1;
            }else{
                high = mid-1;
            }
        }
        return false;
    }
}
